#include "stack_queue.h"

// listNode 类的构造函数实现  
listNode::listNode() : next(nullptr), data(0) {}   
listNode::listNode(int nodeData, listNode* succ) : next(succ), data(nodeData) {}  
  
// MyStack 类的构造函数实现  
 
MyStack::MyStack() : topNode(nullptr), stackSize(0) {}  
  
// MyStack 类的析构函数实现  

MyStack::~MyStack() {  
    while (topNode != nullptr) {  
        listNode* temp = topNode; 
        topNode = topNode->next;   
        delete temp; 
    }  
}  
  
// MyStack 类的 push 方法实现   
bool MyStack::push(const int& value) {  
    listNode* newNode = new listNode(value); 
    if (newNode == nullptr) {  
        return false; 
    }  
    newNode->next = topNode;   
    topNode = newNode;   
    stackSize++;  
    return true; 
}  
  
// MyStack 类的 pop 方法实现  
bool MyStack::pop(int& item) {  
    if (topNode == nullptr) { 
        return false;  
    }  
    listNode* temp = topNode;  
    item = temp->data;  
    topNode = topNode->next;  
    delete temp;   
    stackSize--; 
    return true; 
}  
  
// MyStack 类的 getTop 方法实现  
bool MyStack::getTop(int& item) {  
    if (topNode == nullptr) { 
        return false;  
    }  
    item = topNode->data; 
    return true;   
}

// 检查栈是否为空
bool MyStack::isEmpty() const {
    return topNode == nullptr;
}

void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}



// MyQueue类的构造函数  
MyQueue::MyQueue(const int& capacity) {  
    this->capacity = capacity;  
    queue = new int[capacity]; 
    front =0;
    rear = 0;  
}  
  
// MyQueue类的析构函数  
MyQueue::~MyQueue() {  
    delete[] queue; 
}  
  
// 入队函数  
bool MyQueue::enQueue(const int& value) {  
    if ((rear + 1) % capacity == front) {  
        return false; 
    }  
    queue[rear] = value;  
    rear = (rear + 1) % capacity;  
    return true;  
}  
  
// 出队函数  
bool MyQueue::deQueue(int& item) {  
    if (front == rear) { 
        return false; 
    }  
    item = queue[front];  
    front = (front + 1) % capacity;  
    return true;  
}  
  
// 获取队头元素函数  
bool MyQueue::getFront(int& item) {  
    if (front == rear) {  
        return false;   
    }  
    item = queue[front];  
    return true; 
}  


void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}




// 运算符优先级
int precedence(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}


// 中缀表达式转换为后缀表达式
bool postfixExpression(const string& expression, string& result) {
    MyStack operatorStack;
    result.clear();
    
    for (char c : expression) {
        if (isdigit(c)) { 
            result += c;  
        } else if (c == '(') { 
            operatorStack.push(c);
        } else if (c == ')') { 
            int topOperand;
            while (operatorStack.getTop(topOperand) && topOperand != '(') {
                result += static_cast<char>(topOperand); 
                operatorStack.pop(topOperand);
            }
            if (!operatorStack.getTop(topOperand)) { 
                result = "Expression is wrong!";
                return false;
            }
            operatorStack.pop(topOperand); 
        } else if (precedence(c) > 0) { 
            while (!operatorStack.isEmpty()) {
                int topOp;
                operatorStack.getTop(topOp);
                if (precedence(static_cast<char>(topOp)) >= precedence(c)) {
                    operatorStack.pop(topOp);
                    result += static_cast<char>(topOp); 
                } else {
                    break; 
                }
            }
            operatorStack.push(c); 
        } else {
            result = "Expression is wrong!";
            return false; 
        }
    }

    // 处理完输入后，将栈中所有运算符弹出
    while (!operatorStack.isEmpty()) {
        int topOp;
        operatorStack.pop(topOp);
        if (topOp == '(') { 
            result = "Expression is wrong!";
            return false;
        }
        result += static_cast<char>(topOp);
    }

    return true;
}

// 表达式求值
bool expressionVal(const string& expression, int& result) {
    string postfix;
    if (!postfixExpression(expression, postfix)) {
        result = 0;
        return false;
    }

    MyStack evalStack;
    for (char c : postfix) {
        if (isdigit(c)) {
            evalStack.push(c - '0'); 
        } else { 
            int rightOperand, leftOperand;
            evalStack.pop(rightOperand);
            evalStack.pop(leftOperand);
            int res = 0;

            switch (c) {
                case '+': res = leftOperand + rightOperand; break;
                case '-': res = leftOperand - rightOperand; break;
                case '*': res = leftOperand * rightOperand; break;
                case '/':
                    if (rightOperand == 0) {
                        result = 0;
                        return false; 
                    }
                    res = leftOperand / rightOperand; 
                    break;
                default:
                    result = 0;
                    return false; 
            }
            evalStack.push(res); 
        }
    }

    if (!evalStack.getTop(result)) { 
        result = 0;
        return false; 
    }
    return true;
}



void yanghui(const int& n) {
    // 创建一个队列，分配存储空间，大小为 n*n
    MyQueue queue(n * n);
    // 初始化第一行的第一个元素（杨辉三角的顶端）
    queue.enQueue(1);
    // 外层循环控制打印的行数，i 从 1 开始到 n
    for (int i = 1; i <= n; i++) {
        // 每行的开头入队1
        queue.enQueue(1);
        // 内层循环生成当前行的中间元素
        int start;
        for (int j = 1; j < i; j++) {
            int front, back, value;
            // 获取当前行的前一个元素
            queue.getFront(front);
            queue.deQueue(front); // 出队，准备计算
            // 获取当前行的后一个元素
            queue.getFront(back);
            // 当前元素是前一个元素与后一个元素之和
            value = front + back;
            // 将计算得到的值入队
            queue.enQueue(value);
        }
        // 每行的结尾也入队1（杨辉三角每行的最后一个元素）
        queue.enQueue(1);
        // 移除队列的开头元素（在此例中是一个未使用的元素）
        queue.deQueue(start);
        // 打印当前行的所有元素
        queue.printQueue();
    }
}